// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-21 19:24
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.convertBiNode;

import java.util.ArrayList;
import java.util.List;

public class convertBiNode_ {
    ArrayList<Integer> treeVal = new ArrayList<>();

    public TreeNode convertBiNode(TreeNode root) {
        // 使用先序遍历确定值的顺序,每一个节点的左子树为空
        // 节点的右子树为下一个值
        preFind(root);
        return constructTree(treeVal, 0);
    }

    public void preFind(TreeNode root) {
        // 树的中序遍历，并且将存在的树的节点值按顺序返回
        if (root != null) {
            preFind(root.left);
            treeVal.add(root.val);
            preFind(root.right);
        }
    }

    public TreeNode constructTree(List<Integer> val, int i) {
        // 根据val构造指定结构树
        if (i < val.size()) {
            TreeNode treeNode = new TreeNode(val.get(i));
            treeNode.left = null;
            treeNode.right = constructTree(val, ++i);
            return treeNode;
        } else {
            return null;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
